//https://www.nowcoder.com/practice/48d2ff79b8564c40a50fa79f9d5fa9c7?tpId=13&tqId=2276769&ru=%2Fpractice%2F2237b401eb9347d282310fc1c3adb134&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 解法1:滑动窗口
// 解法2:动态规划

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>

using namespace std;

class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        //哈希表记录窗口内非重复的字符
        unordered_map<char, int> mp;
        int res = 0;
        //设置窗口左右边界
        for (int left = 0, right = 0; right < s.length(); right++) {
            //窗口右移进入哈希表统计出现次数
            mp[s[right]]++;
            //出现次数大于1，则窗口内有重复
            while (mp[s[right]] > 1){
                //窗口左移，同时减去该字符的出现次数
                mp[s[left]]--;
                left++;
            }
                
            //维护子串长度最大值
            res = max(res, right - left + 1);
        }
        return res;
    }
};


#include <map>
#include <cstddef>
class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        if (s.size() == 1) return 1;

        std::map<char,size_t> char_index_map;
        size_t cur_res = 0;
        size_t max_res = 0;

        for(size_t left=0,right=0;right<s.size();++right){
            char cur_char= s[right];
            if (char_index_map.find(cur_char) == char_index_map.end()) {
                ++cur_res;
            }else{
                size_t first_index = char_index_map.find(cur_char)->second;
                while (left<=first_index) {
                    char_index_map.erase(s[left]);
                    ++left;
                }
                cur_res = right - left + 1;
            }
            char_index_map[cur_char] = right;
            max_res = std::max(max_res,cur_res);
        }
        return max_res;
    }
};